A wide variety of devices store computer data. These devices vary greatly in their storage capacities and speeds. For example, a disk typically stores much more data than a memory chip. A memory chip, on the other hand, can often provide access to data much faster than a disk.
Many systems combine different types of storage devices to provide both large storage capacity and fast access to data. For example, a common technique for speeding data access involves caching (pronounced xe2x80x9ccashingxe2x80x9d) data in high-speed memory. For instance, a data cache may store a copy of some data also stored by a slower storage device. When a request for the cached data arrives, a system can quickly respond to the request by accessing the cached copy instead of waiting for data retrieval by the slower storage device.
In general, in one aspect, the description includes a method of data storage address translation. The method includes receiving a first address in a first address space, traversing a trie based on the first address, and determining a second address based on the traversal.
Embodiments may include one or more of the following features. The first address may have a different (e.g., larger) address space than the second address. The trie may include at least one leaf identifying an address in the second address space. The second address may be an address of a cache memory. The first address may be an address of permanent data storage. The second address associated with the first address may dynamically change, for example, based on changing cache contents.
The method may further include determining whether the cache stores information identified by the first address. Traversing the trie may include performing an operation on the first address and traversing the trie using the operation results.
The trie may be implemented as a multi-dimensional array where an index of a dimension of the array corresponds to different trie branches. Traversing such a trie may include repeatedly indexing into the array using a portion of the first address.
In general, in another aspect, the description includes a data storage system. The system includes a storage area having a first address space, a cache having a second address space, and instructions for causing a processor to receive a first address in the first address space, traverse a trie based on the first address, and determine a second address in the second address space based on the traversal.
In general, in another aspect, the description includes a computer program product, disposed on a computer readable medium, for data storage address translation. The computer program includes instructions for causing a processor to receive a first address within a first address space, traverse a trie based on the first address, and determine a second address based on the traversal.
In general, in another aspect, the description includes a method of data storage address translation at a system having a storage area composed of different physical devices, a shared cache for caching blocks of data in the storage area, and connections to different host processors. The method includes receiving a storage area address within a storage area address space based on a request received from one of the host processors, traversing a trie based on the storage area address, the traversing identifying a trie leaf identifying a cache address in a cache address space, and changing the cache address associated with the trie leaf based on an alteration of cache contents.
In general, in another aspect, the description includes a memory for storing data for access by an application program being executed on a data processing system. The memory includes a data structure that includes information corresponding to a trie having leaves identifying different respective cache addresses.
Advantages will become apparent in view of the following description, including the figures and the claims.